public class MyTrue {
    public static class Node
    {
        char value;
        Node left;
        Node right;
        public Node (char value){
            this.value=value;
        }
    }
    // Node head;
    public  Node inti(){
        Node node1=new Node('a');
        Node node2=new Node('b');
        Node node3=new Node('c');
        Node node4=new Node('d');
        Node node5=new Node('e');
        Node node6=new Node('f');
        Node node7=new Node('g');
        Node node8=new Node('i');
        Node node9=new Node('h');
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;
        node5.right=node8;
        node5.left=node9;

        return node1;
    }
    public void perOrder(Node head1){
        if(head1==null) return;
        System.out.print(head1.value+" ");
        perOrder(head1.left);
        perOrder(head1.right);
    }

    public void inOrder(Node head1){
        if(head1==null) return;
        inOrder(head1.left);
        System.out.print(head1.value+" ");
        inOrder(head1.right);
    }

    public  int nodeSize=0;
    public void lastOrder(Node head1){
        if(head1==null) return;
        lastOrder(head1.left);
        lastOrder(head1.right);
        System.out.print(head1.value+" ");
    }
    public  void getNodeSize1(Node root){
        if(root==null) return;
        nodeSize++;
        getNodeSize1(root.left);
        getNodeSize1(root.right);
    }

    public int getNodeSize2(Node root){
        if(root==null) return 0;
        return getNodeSize2(root.left)+getNodeSize2(root.right)+1;
    }
        public int leaf;
    public void getLeafNodeCount(Node root){
        if(root==null) return;
        if(root.right==null&&root.left==null) {
            leaf++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }
    public int getLeafNodeCount2(Node root){
        if(root==null) return 0;
        if(root.right==null&&root.left==null) {
            return 1;
        }
        return  getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }


    //每层结点数
    public int getLeveNodeCount(Node root,int k){
        if(root==null) return 0;
        if(k==1) return 1;
        return getLeveNodeCount(root.left,k-1)+getLeveNodeCount(root.right,k-1);
    }

    //树高度
    public int getHeight(Node root) {
        if(root==null) return 0;
        int leftHeight=getHeight(root.left)+1;
        int rightHeight=getHeight(root.right)+1;
        return Math.max(leftHeight,rightHeight);
    }
    //找特定节点值
    public Node find(Node root,char key){
        if(root==null) return null;
        if(root.value==key) return  root;
        Node left=find(root.left,key);
        if(left!=null) return left;
        Node right=find(root.right,key);
        if(right!=null) return right;
        return null;
    }

}
